πŸ’‘ DP (Dynamic Programming)

@Seongukbaek Posted May 13, 2022 Β· Updated May 13, 2022 Β· 5 min read

🧷 동적 κ³„νšλ²• (DP)

λ³΅μž‘ν•œ 문제λ₯Ό κ°„λ‹¨ν•œ μ—¬λŸ¬ 개의 문제둜 λ‚˜λˆ  ν‘ΈλŠ” λ°©λ²•μœΌλ‘œ, 큰 μ˜λ―Έμ—μ„œ λΆ„ν•  정볡과 같은 μ ‘κ·Ό 방식을 μ˜λ―Έν•œλ‹€.

ν•œ κ°€μ§€ λ¬Έμ œμ— λŒ€ν•΄, 단 ν•œ 번만 풀도둝 λ§Œλ“€μ–΄μ£ΌλŠ” μ•Œκ³ λ¦¬μ¦˜μœΌλ‘œ, λ™μΌν•œ 연산을 λ°˜λ³΅ν•˜μ§€ μ•ŠλŠ”λ‹€.

  • μ‹€ν–‰ μ‹œκ°„μ„ 쀄이기 μœ„ν•΄ 많이 μ΄μš©λ˜λŠ” μ•Œκ³ λ¦¬μ¦˜ (μ΅œμ ν™” μ•Œκ³ λ¦¬μ¦˜)

    • νš¨μœ¨μ„± ν…ŒμŠ€νŠΈκ°€ μžˆλŠ” 경우, DPλ‚˜ 이진 탐색을 많이 μ‚¬μš©ν•œλ‹€κ³ λ“€ ν•œλ‹€...

  • Optimal Substructureμ—μ„œ 효과λ₯Ό λ°œνœ˜ν•œλ‹€.

    • Optimal Substructure: 닡을 κ΅¬ν•˜κΈ° μœ„ν•΄ 이미 ν–ˆλ˜ λ™μΌν•œ 연산을 λ°˜λ³΅ν•˜λŠ” ꡬ쑰둜, μ΅œμ ν™” 문제의 λͺ¨λ“  ν•˜μœ„ μ†”λ£¨μ…˜μ€ 졜적의 μ†”λ£¨μ…˜μ΄λ‹€. (Principle of Optimality)

λΆ„ν•  정볡과 DP의 차이점? : 문제λ₯Ό λ‚˜λˆ„λŠ” 방식에 μžˆμ–΄ 차이가 μžˆλ‹€. 동적 κ³„νšλ²•μ—μ„œ, μ–΄λ–€ λΆ€λΆ„ λ¬Έμ œλŠ” 두 개 μ΄μƒμ˜ 문제λ₯Ό ν‘ΈλŠ” 데 μ‚¬μš©λ  수 μžˆμ–΄ 이 문제의 닡을 μ—¬λŸ¬ 번 κ³„μ‚°ν•˜μ§€ μ•Šκ³  ν•œ 번만 κ³„μ‚°ν•œ ν›„ κ²°κ³Όλ₯Ό μž¬μ‚¬μš©ν•˜λŠ” 방식을 μ·¨ν•œλ‹€.

πŸͺš 쑰건

  • μž‘μ€ λ¬Έμ œμ—μ„œ 반볡이 λ°œμƒ
  • 같은 λ¬Έμ œλŠ” 항상 같은 μ •λ‹΅

μœ„ 두 κ°€μ§€ 쑰건을 μΆ©μ‘±ν•œλ‹€λ©΄, 동적 κ³„νšλ²•μ„ μ‚¬μš©ν•΄ 문제λ₯Ό ν’€ 수 μžˆλ‹€. 그리고 ν•œ 번 κ³„μ‚°ν•œ κ²°κ³Όλ₯Ό μ €μž₯ν•˜κΈ° μœ„ν•΄ Memoization을 μ‚¬μš©ν•œλ‹€.

Memoization : ν•œ 번 κ³„μ‚°ν•œ λ¬Έμ œλŠ” λ‹€μ‹œ κ³„μ‚°ν•˜μ§€ μ•Šλ„λ‘ μ €μž₯해두고 μž¬μ‚¬μš©ν•˜λŠ” 방식

πŸͺš 예제

κ°€μž₯ 유λͺ…ν•œ 예 쀑 ν•˜λ‚˜λŠ” 이항 κ³„μˆ˜(binomial coefficient)의 계산이닀. 이항 κ³„μˆ˜(nr)(\begin{matrix}n\\r\\ \end{matrix})λŠ” n개의 μ„œλ‘œ λ‹€λ₯Έ μ›μ†Œ 쀑 r개의 μ›μ†Œλ₯Ό μˆœμ„œμ—†μ΄ κ³¨λΌλ‚΄λŠ” λ°©λ²•μ˜ 수λ₯Ό λ‚˜νƒ€λ‚Έλ‹€.

  • 그리고 이 점화식을 μž¬κ·€ ν˜ΈμΆœμ„ μ΄μš©ν•˜μ—¬ κ΅¬ν˜„ν•˜λ©΄ μ•„λž˜μ™€ κ°™λ‹€.
int bino(int n, int r) { if (r == 0 || n == r) return 1; return bino(n - 1, r - 1) + bino(n - 1, r); }
  • μž¬κ·€ ν˜ΈμΆœμ„ μˆ˜ν–‰ν•˜λŠ” κ³Όμ •μ—μ„œ, λ™μΌν•œ 연산이 μ€‘λ³΅μ μœΌλ‘œ ν˜ΈμΆœλœλ‹€. 그리고 μ΄λŸ¬ν•œ 쀑볡 계산은 n이 증가할 λ•Œλ§ˆλ‹€ κΈ°ν•˜κΈ‰μˆ˜μ μœΌλ‘œ μ—°μ‚°λŸ‰μ΄ μ¦κ°€ν•˜λ„λ‘ λ§Œλ“ λ‹€.
  • λ”°λΌμ„œ, 각 n,r 쑰합에 λŒ€ν•΄ 닡을 μ €μž₯ν•˜λŠ” 배열을 λ§Œλ“€μ–΄, 각 μž…λ ₯에 λŒ€ν•œ λ°˜ν™˜ 값을 μ €μž₯ν•˜λ„λ‘ λ³€κ²½ν•œλ‹€.

    • 이미 μ €μž₯된 값이 μžˆλ‹€λ©΄ 이λ₯Ό μž¬μ‚¬μš©ν•˜κ³ , κ·Έλ ‡μ§€ μ•Šλ‹€λ©΄ 직접 κ³„μ‚°ν•œ ν›„ 배열에 값을 μ €μž₯ν•œλ‹€.
    • 즉, Memoization을 μ‚¬μš©ν•΄ μ΅œμ ν™”λ₯Ό μˆ˜ν–‰ν•œλ‹€.
// -1둜 μ΄ˆκΈ°ν™” int[][] cache = new int[30][30]; int bino2(int n, int r) { if (r == 0 || n == r) return 1; if (cache[n][r] != -1) return cache[n][r]; return cache[n][r] = bino2(n - 1, r - 1) + bino2(n - 1, r); }

πŸͺš κ΅¬ν˜„ 방식

동적 κ³„νšλ²•μ„ κ΅¬ν˜„ν•˜λŠ” 방식에 μžˆμ–΄ 2κ°€μ§€κ°€ κ°€λŠ₯ν•˜λ‹€.

  • Bottom-up: μž‘μ€ λ¬Έμ œλ“€λΆ€ν„° ν•΄κ²°ν•˜λ©΄μ„œ 전체 닡을 κ΅¬ν•˜λŠ” 방식

    • ν”νžˆ λ°˜λ³΅λ¬Έμ„ μ‚¬μš©ν•΄ κ΅¬ν˜„ν•˜κ³ , μž¬κ·€ ν˜ΈμΆœμ„ μ‚¬μš©ν•˜μ§€ μ•Šμ•„ μ‹œκ°„κ³Ό λ©”λͺ¨λ¦¬ μ‚¬μš©λŸ‰μ„ 쀄일 수 μžˆλ‹€λŠ” μž₯점이 μžˆλ‹€.
  • Top-down: κ°€μž₯ 큰 문제λ₯Ό λ°©λ¬Έ ν›„ μž‘μ€ 문제λ₯Ό ν˜ΈμΆœν•΄ 닡을 κ΅¬ν•˜λŠ” 방식

    • ν”νžˆ μž¬κ·€ ν˜ΈμΆœμ„ μ‚¬μš©ν•΄ κ΅¬ν˜„ν•˜κ³ , 점화식을 μ§κ΄€μ μœΌλ‘œ μ΄ν•΄ν•˜κΈ° μ‰½λ‹€λŠ” μž₯점이 μžˆλ‹€.

πŸ“• μ°Έκ³ 

@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€